import java.util.*;

public class Demo2 {


    public static void main(String[] args) {

    }


    public int[] getLeastNumbers(int[] nums, int k) {
        qsort3(nums,0,nums.length-1,k);
        int[] ret = new int[k];

        for(int i = 0;i<k;i++){
            ret[i] = nums[i];
        }
        return ret;


    }

    private void qsort3(int[] nums, int l, int r, int k) {
        //找随机数
        int key = nums[new Random().nextInt(r-l+1)+l];
        int left = l-1;
        int right = r+1;
        int i = l;
        while (i<right){
            if (nums[i]<key){
                swap3(nums,++left,i++);
            }else if(nums[i]==key){
                i++;
            }else {
                swap3(nums,--right,i);
            }
        }

        int a = left-l+1;
        int b = right-left-1;
        if (a>k){
            qsort3(nums,l,left,k);
        }else if(a+b>=k){
            return;
        }else {
            qsort3(nums,right,r,k-a-b);
        }

    }

    private void swap3(int[] nums, int l, int r) {
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;

    }


    public int[] getLeastNumbers2(int[] arr, int k) {
        List<Integer> ret = new ArrayList<>();
        qsort2(arr,0,arr.length-1,k,ret);
        int[] ll = new int[k];
        for(int i=0;i<k;i++){
            ll[i] = ret.get(i);
        }
        return ll;
    }

    private void qsort2(int[] nums, int l, int r, int k, List<Integer> ret) {
        if (l==r){
            ret.add(nums[l]);
            return;
        }

        int key = nums[new Random().nextInt(r-l+1)+1];

        int left = l-1;
        int right = r+1;
        int i = l;
        while (i<right){
            if (nums[i]<key){
                swap2(nums,++left,i++);
            }else if(nums[i] == key){
                i++;
            }else {
                swap2(nums,--right,i);
            }
        }

        //判断
        int a = left-l+1;
        int b = right-left+1;
        if (a>=k){
            qsort2(nums,l,left,k,ret);
        }else if(a+b>=k){
            for (int j=l;i<k;j++){
                ret.add(nums[j]);
            }
        }else {
            for (int j=l;i<a+b;j++){
                ret.add(nums[j]);
            }
            qsort2(nums,right,r,k-a-b,ret);
        }

    }

    private void swap2(int[] nums, int l, int r) {
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }


    public int findKthLargest(int[] nums, int k) {
        int ret = qsort1(nums,0,nums.length-1,k);
        return ret;


    }

    private int qsort1(int[] nums, int l, int r, int k) {
        if (l==r){
            return nums[l];
        }
        //随机数
        int key = nums[new Random().nextInt(r-l+1)+l];

        int left = l-1;
        int right = r+1;
        int i = l;
        while (i<right){
            if (nums[i]<key){
                swap1(nums,++left,i++);
            }else if(nums[i]==key){
                i++;
            }else{
                swap1(nums,--right,i);
            }
        }

        //分类讨论
        int b = right-left-1;
        int c = r-right+1;
        if (c >= k){
            return qsort1(nums,right,r,k);
        }else if(b+c>=k){
            return key;
        }else {
            return qsort1(nums,l,left,k-b-c);
        }

    }
    private void swap1(int[] nums, int l, int r) {
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;

    }


    public int[] sortArray(int[] nums) {
        qsort(nums,0,nums.length-1);
        return nums;



    }

    private void qsort(int[] nums, int l, int r) {
        if (l>=r){
            return;
        }
        //找基准值
        int key = nums[new Random().nextInt(r-l+1)+l];
        int left = l-1;
        int right = r+1;
        int i = l;
        while (i<right){
            if (nums[i]<key){
                swap(nums,++left,i++);
            }else if(nums[i] == key){
                i++;
            }else {
                swap(nums,--right,i);
            }
        }
        qsort(nums,l,left);
        qsort(nums,right,r);


    }

    private void swap(int[] nums, int l, int r) {
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;

    }

    public void sortColors(int[] nums) {
        int i = 0;
        int left = -1;
        int right = nums.length;
        while (i<right){
            if (nums[i]==0){
                left++;
                int tmp = nums[left];
                nums[left] = nums[i];
                nums[i] = tmp;
                i++;
            }else if(nums[i]==1){
                i++;
            }else {
                right--;
                int tmp = nums[right];
                nums[right] = nums[i];
                nums[i] = tmp;
            }
        }
    }









    public int minNumberOfFrogs(String croakOfFrogs) {

        char[] croakOf = croakOfFrogs.toCharArray();
        String t = "croak";
        int n = t.length();

        int[] hash = new int[n];//数组模拟hash表

        Map<Character,Integer> index = new HashMap<>();
        for(int i = 0;i<n;i++){
            index.put(t.charAt(i),i);
        }
        for (char ch:croakOf){
            if (ch==t.charAt(0)){
                if (hash[n-1] != 0){
                    hash[n-1]--;
                }
                hash[0]++;
            }else {
                int i = index.get(ch);
                if (hash[i-1]==0){
                    return -1;
                }else {
                    hash[i-1]--;
                    hash[i]++;
                }
            }
        }

        for (int i=0;i<n-1;i++){
            if (hash[i]!=0){
                return -1;
            }
        }
        return hash[n-1];

    }


    //数青蛙
    public int minNumberOfFrogs1(String croakOfFrogs) {
        int[] hash = new int[26];

        char[] arr = croakOfFrogs.toCharArray();
        //遍历字符串
        for(int i=0;i<croakOfFrogs.length();i++){
            if (arr[i] == 'c'){
                if (arr['k'-'a'] == 0 ){
                    hash['c'-'a']++;
                }else {
                    hash['k'-'a']--;
                    hash['c'-'a']++;
                }
            }
            if (arr[i] == 'r'){
                if (arr['c'-'a']==0){
                    return -1;
                }else {
                    hash['c'-'a']--;
                    hash['r'-'a']++;
                }
            }
            if (arr[i] == 'o'){
                if (arr['r'-'a']==0){
                    return -1;
                }else {
                    hash['r'-'a']--;
                    hash['o'-'a']++;
                }
            }
            if (arr[i] == 'a'){
                if (arr['o'-'a']==0){
                    return -1;
                }else {
                    hash['o'-'a']--;
                    hash['a'-'a']++;
                }
            }
            if (arr[i] == 'k'){
                if (arr['a'-'a']==0){
                    return -1;
                }else {
                    hash['a'-'a']--;
                    hash['k'-'a']++;
                }
            }

        }
        if (hash['k'-'a']*5 == croakOfFrogs.length()){
            return hash['k'-'a'];
        }else{
            return -1;
        }

    }



    public String countAndSay(int n) {
        String ret = "1";
        for (int i=1;i<n;i++){//n-1此
            StringBuilder tmp = new StringBuilder();
            for (int left = 0,right=0;right<ret.length();){
                while (right<ret.length()&&ret.charAt(left) == ret.charAt(right)){
                    right++;
                }
                tmp.append(Integer.toString(right-left));
                tmp.append(ret.charAt(left));
                left=right;
            }
            ret= tmp.toString();

        }
        return ret;



    }


    public String countAndSay1(int n) {

        if(n==1){
            return "1";
        }


        String str = "1";
        String tmp = "";
        for(int i=1;i<n;i++){
            int right = 0;
            int left = 0;
            tmp="";
            while (right<str.length()){
                if (right<str.length() && str.charAt(right)==str.charAt(left)){
                    right++;
                }
                if(right<str.length() && str.charAt(right)!=str.charAt(left)){
                    tmp += (right-left)+""+str.charAt(right-1);
                    left=right;
                }
            }
            tmp += (right-left)+""+str.charAt(right-1);
            str = tmp;

        }
        return str;

    }


    public String convert(String s, int numRows) {

        int d = 2*numRows-2,n=s.length();
       StringBuilder ret = new StringBuilder();


       if (numRows==1){
           return s;
       }
       //第一行
        for (int i=0;i<n;i+=d){
            ret.append(s.charAt(i));
        }
        //处理中间行
        for(int k=1;k<numRows-1;k++){
            for(int i=k,j=d-i;i<n||j<n;i+=d,j+=d){
                if (i<n){
                    ret.append(s.charAt(i));
                }
                if (j<n){
                    ret.append(s.charAt(j));
                }
            }
        }
        //最后一行
        for(int i = numRows-1;i<n;i+=d){
            ret.append(s.charAt(i));
        }
        return ret.toString();





    }

    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int ret = duration;
        for(int i = 0;i<timeSeries.length-1;i++){
            int x= timeSeries[i+1] - timeSeries[i];
            if (x>=duration){
                ret+=duration;
            }else {
                ret+=x;
            }
        }
        return ret;



    }

    public String modifyString(String s) {
        char[] arr = s.toCharArray();
        for (int i=0;i<s.length();i++){
            if (arr[i] == '?'){
                for(int j=0;j<26;j++){
                    arr[i] = (char) ('a'+j);
                    if ( i>=1&& i<s.length()-1 && arr[i-1] != arr[i] && arr[i] != arr[i+1]){
                        break;
                    }else if(i==0 && arr[i] != arr[i+1]){
                        break;
                    }else if (i==s.length()-1 && arr[i-1] != arr[i]){
                        break;
                    }
                }
            }
        }
        return new String(arr);

    }
}
